'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-10-13 18:35:15
LastEditTime: 2025-10-13 18:46:32
'''


class Node:

    __slot__ = ["son", "end"]
    def __init__(self):
        self.son = {}
        self.end = False

class Trie:

    def __init__(self):

        self.root = Node()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node()


            cur = cur.son[c]
        cur.end = True
    
    def find(self, word):

        cur = self.root
        for c in word:
            if c not in cur.son:
                return 0
            
            cur = cur.son[c]

        return 2 if cur.end else 1
    
    def search(self, word):
        return self.find(word) == 2
    
    def startsWith(self, prefix):
        return self.find(prefix) != 0

